import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 优选算法day2
 * User: 姚东名
 * Date: 2024-11-12
 * Time: 10:08
 */
public class Test {
    // 1. 和为 s 的两个数字（easy）
    public int[] twoSum(int[] price, int target) {
        int left = 0;
        int right = price.length - 1;
        while (left < right) {
            int sum = price[left] + price[right];
            if (sum > target) {
                right--;
            } else if (sum < target) {
                left++;
            } else {
                return new int[]{price[left], price[right]};
            }
        }
        return new int[]{0};
    }

    // 2. 三数之和（medium）
    public List<List<Integer>> threeSum(int[] nums) {
        // 申请一个集合进行装载数组
        List<List<Integer>> ret = new ArrayList<>();

        // 1. 先对数组进行一个升序排序
        Arrays.sort(nums);

        // 2. 利用双指针来解决问题
        int n = nums.length;
        for (int i = 0; i < n; ) {
            // 小优化：
            if (nums[i] > 0) {
                break;
            }
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];
                // int target = -nums[i];
                if (sum + nums[i] > 0) {
                    right--;
                } else if (sum + nums[i] < 0) {
                    left++;
                } else {
                    ret.add(new ArrayList<Integer>(
                            Arrays.asList(nums[i], nums[left], nums[right]))
                    );
                    left++;
                    right--;
                    // 3.1 对left到right范围进行去重
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            // 3.2 对i进行去重
            i++;
            while (i < n && nums[i] == nums[i - 1]) {
                i++;
            }
        }
        return ret;
    }

    // 3. 四数之和（medium）
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // 使用List集合对数组进行装载
        List<List<Integer>> ret = new ArrayList<>();

        // 1. 对数组进行升序排序
        Arrays.sort(nums);

        // 2. 利用双指针解决问题：
        int  n = nums.length;
        for (int i = 0; i < n; ) {
            for (int j = i + 1; j < n; ) {
                int left = j + 1;
                int right = n - 1;
                long aim = (long)target - nums[i] - nums[j];
                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum > aim) {
                        right--;
                    } else if (sum < aim) {
                        left++;
                    } else {
                        ret.add(
                                Arrays.asList(nums[i], nums[j], nums[left], nums[right])
                        );
                        left++;
                        right--;
                        // 3.1 对left到right范围进行去重
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                // 3.2 对j到n范围进行去重
                j++;
                while (j < n && nums[j] == nums[j - 1]) {
                    j++;
                }
            }
            // 3.3 对i到n范围进行去重
            i++;
            while (i < n && nums[i] == nums[i - 1]) {
                i++;
            }
        }
        return ret;
    }

    // 4. 长度最小的子数组（medium）
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int left = 0, right = 0;
        int sum = 0;
        int len = Integer.MAX_VALUE;
        // 判断
        for (; right < n; right++) {
            // 入窗口
            sum += nums[right];
            while (sum >= target) {
                // 更新结果
                len = Math.min(len, right - left + 1);
                // 出窗口
                sum -= nums[left++];
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }

    // 5. 无重复的字符的最长子串（medium）
    public int lengthOfLongestSubstring(String ss) {
        // 将字符串转化为字符串数组，里面每个元素是
        char[] s = ss.toCharArray();

        // 用数组模拟实现哈希表hash
        int[] hash = new int[128];
        int ret = 0;
        int left = 0, right = 0, len = ss.length();

        while (right < len) {
            // 1. right进窗口
            hash[s[right]]++;
            // 2. 判断：遇到重复的就弹出哈希表
            while (hash[s[right]] > 1) {
                // 3. left出窗口
                hash[s[left++]]--;
            }
            //4. 更新结果
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;
    }

    // 方式二：
    public static int lengthOfLongestSubstring2(String s) {
        // 边界条件：如果字符串为空，返回0
        if (s == null || s.length() == 0) {
            return 0;
        }

        // 使用HashSet来存储当前窗口中的字符
        Set<Character> set = new HashSet<>();
        int maxLength = 0; // 最长无重复字符子串的长度
        int left = 0; // 窗口的左边界

        // 遍历字符串的每一个字符
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);

            // 如果当前字符已经存在于HashSet中，说明出现了重复字符
            // 此时需要移动左边界，并从HashSet中移除左边界对应的字符，直到当前字符不再重复
            while (set.contains(currentChar)) {
                set.remove(s.charAt(left));
                left++;
            }

            // 将当前字符添加到HashSet中
            set.add(currentChar);

            // 更新最长无重复字符子串的长度
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    public int lengthOfLongestSubstring3(String s) {
        if (s.length() == 0) {
            return 0;
        }
        // 1. 申请一个HashSet（具有去重的效果）来存储当前的窗口的字符
        Set<Character> set = new HashSet<>();
        int maxLength = 0;
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // 2. left出窗口
            while (set.contains(c)) { // 3. 判断
                set.remove(s.charAt(left));
                left++;
            }
            // 1. right进窗口
            set.add(c);
            // 4. 更新结果
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        // 创建一个字符串
        String str = "Hello, World!";

        // 使用 toCharArray() 方法将字符串转换为字符数组
        char[] charArray = str.toCharArray();

        // 输出字符数组中的每个字符
        for (char c : charArray) {
            System.out.print(c + " ");
        }
    }
}
